perm filename SEC5.TEX[105,CSD] blob
sn#536184 filedate 1980-09-18 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \specialbegin{Arrays} \sendindex{Arrays}
C00024 00003 \specialbegin{Desk Checking of Programs} \sendindex{Desk Checking}
C00031 00004 \specialbegin{Diagnosing Incorrect Results of Programs}
C00036 00005 \specialbegin{Design of Conditional Commands}
C00040 00006 % B example continued.
C00043 00007 % B example continued.
C00046 00008 % B example continued.
C00047 00009 \specialbegin{Avoiding Redundant Effort in Programming}
C00070 ENDMK
C⊗;
\specialbegin{Arrays} \sendindex{Arrays}
Suppose we choose to print the values of
$f↓{1}$,$f↓{2}$,$\ldotss$,$f↓{24}$ from the example
of the rabbit breeder in three columns:
\threecolalign{
$f↓{1}$⊗$f↓{9}$⊗$f↓{17}$\cr
$f↓{2}$⊗$f↓{10}$⊗$f↓{18}$\cr
.⊗.⊗.\cr
.⊗.⊗.\cr
.⊗.⊗.\cr
$f↓{8}$⊗$f↓{16}$⊗$f↓{24}$\cr
}%end of threecolalign
We could not complete the printing of the first line until $f↓{17}$ had been
computed. This situation seems to call for having a large number of storage
variables to retain the values of at least $f↓{1}$,$f↓{2}$,$\ldotss$,$f↓{16}$, until they can be
printed. Just as (by iteration) we can readily construct a large family of
similar commands, we can also construct a large family of similar program
variables, called an {\sl array}. \sendindex{array} We create for this
purpose an array of 24
storage variables, by the {\sl array declaration}. \sendindex{array declaration}
\wuncode{VAR X : ARRAY [1..24] OF INTEGER}
which creates the integer variables called {\tt X[1],X[2],$\ldotss$,X[24]} when the block
is entered. We can modify our previous computation of $f↓{1}$,$f↓{2}$,$\ldotss$,$f↓{24}$
so that whenever $f↓{i}$ is computed, its value is given to {\tt X[$i$]}. Then the
program becomes:
\startcode
PROGRAM FIBTABLE;
VAR I,J : INTEGER;
X : ARRAY [1..24] OF INTEGER;
BEGIN
X[1] := 1; (* F(1) = 1 *)
X[2] := 1; (* F(2) = 1 *)
(* COMPUTE X[3],X[4],$\ldotss$,X[24] *)
FOR I:= 3 TO 24 DO
(* ALREADY X[1] = F(1),$\ldotss$,X[I-1] = F(I-1) *)
X[I] := X[I-1] + X[I-2]; (* X[1] = F(1),$\ldotss$,X[I] = F(I) *)
(* PRINT THE THREE-COLUMN TABLE *)
FOR J:= 1 TO 8 DO
WRITELN(X[J],X[J+8],X[J+16])
END.
\endcode
Notice in the last line, for example, that {\tt X[J+8]} is not a single program
variable, but may be any of eight different storage variables depending on the
value of {\tt J}.
The use of arrays has two benefits. One is the brevity of the
declaration; to create twenty-four variables otherwise would have required a
declaration like
\startcode
VAR X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,
X14,X15,X16,X17,X18,X19,X20,X21,X22,X23,X24 : INTEGER;
\endcode
The other advantage is that the variables created by an array declaration are
related. We may write {\tt X[$\Escr$]}, where $\Escr$ is an expression
which takes on
different integer values between one and twenty-four at different times, to
refer to different variables of the same array at different times. A single
command is thereby
able to change the value of any one of the variables in the array as
{\tt X[I] := X[I-1] + X[I-2]} does, or to use the value of any of the
variables, as the printing command above does.
In an expression like {\tt X[I+J]} where {\tt X} is an array name, the expression
{\tt I+J} in square brackets is called the {\sl subscript}. \sendindex{subscript}
It is evaluated to find which
variable {\tt X[I+J]} designates; if {\tt I} = 3 and {\tt J} = 8, {\tt X[I+J]}
designates the variable {\tt X[11]}. Strictly speaking, {\tt X[I+J]}
is not a variable, but an
expression designating a variable; however, a loose usage is customary in which
such an expression is called a variable.
Arrays may also be created in which the variables have two or more
subscripts. Suppose we wanted to write a computer program to keep a record of
the frequency of occurrences of digrams (two-letter pairs) in English text.
(In the first sentence of this paragraph, the digram ``AR'' occurs twice;
``ZQ'' does not occur at all.) We would probably create an array {\tt F} by a
declaration like
\wuncode{VAR F : ARRAY [1..26,1..26] of INTEGER;}
in which the variable {\tt F[1,18]} would be used to hold a count of the number of
digrams ``AR'', since ``A'' is the first and ``R'' the eighteenth letter of the
English alphabet. Upon finding in a text a digram consisting of the i-th
letter of the alphabet followed by the j-th, the program would execute the command
{\tt F[I,J] := F[I,J]+1} to increase the count for that digram.
The general form of an array declaration is
\wuncode{VAR $\Iscr ↓1$,$\Iscr ↓2,$ $\ldotss$,$\Iscr ↓n$ : ARRAY
[$\Kscr↓{11}$..$\Kscr↓{12}$,$\Kscr↓{21}$..$\Kscr↓{22}$,$\ldotss$,$\Kscr↓{m1}$..$\Kscr↓{m2}$] OF $\Tscr$;}
where $n ≥ 1$, $m ≥ 1$, $\Tscr$ is any type, and the {\sl array bounds}
$\Kscr ↓{11}$, $\Kscr ↓{12}$, $\ldotss$, $\Kscr ↓{m2}$ are integer constants.
The array declaration creates the variables
\wuncode{$\Iscr ↓{j}$[$y ↓{1}$,$y ↓{2}$,$\ldotss$,$y ↓{m}$]}
for each $j\ (1 ≤ j ≤ n)$ and for each combination of integers
$y ↓{1}$, $y ↓{2}$, $\ldotss$, $y ↓{m}$ which lie in the respective ranges
$(\Kscr ↓{11},\Kscr ↓{12}), (\Kscr ↓{21},\Kscr ↓{22}), \ldotss, (\Kscr ↓{m1},\Kscr ↓{m2})$;
that
is, for which $\Kscr ↓{i1} ≤ y↓{i} ≤ \Kscr ↓{i2} \ (1 ≤ i ≤ m)$.
For example,
\wuncode{VAR X,Y: ARRAY[1..2,-2..0] OF REAL;}
creates the array of storage variables
\startcode
X[1,-2] X[1,-1] X[1,0]
X[2,-2] X[2,-1] X[2,0]
Y[1,-2] X[1,-1] X[1,0]
Y[2,-2] Y[2,-1] Y[2,0]
\endcode
\noindent
where the first subscript lies between 1 and 2, and the second between -2 and 0.
\example
To read 100 numbers and print them in reverse order:
\startcode
VAR X : ARRAY [1..100] OF REAL;
BEGIN
FOR J:= 1 TO 100 DO READ(X[J]);
FOR I:= 100 DOWNTO 1 DO WRITELN(X[I])
END.
\endcode
\exercise
Design a program to read 100 numbers and print them in four
vertical columns.
\endexercise
\exercise
Design a program to read 100 numbers, and print the mean
(average), and the average deviation from the mean, of the numbers. (The
deviation of a number $X$ from the mean $M$ is defined as $ABS(X-M)$, the
absolute value of the difference between the number and the mean; if the
numbers were 2, 5, and 7, the mean would be $14/3$,
and the average deviation from the mean would be $16/9$.
\endexercise
\specialbegin{Desk Checking of Programs} \sendindex{Desk Checking}
It is a mistake to expect the computer to find the errors in your
programs. Many errors are found much more easily by checking methods which
depend on understanding what the program is doing, before the computer ever
sees the program.
The first step is to get a grammatically correct program.
\bitem Use a light colored pencil or marking pen to circle each comment,
checking that there is no other {\tt (*} or {\tt *)} in the comment.
From here on, ignore the comments, as they are ignored by the translator.
\bitem Find the first {\tt END} in the program, and draw a line in the left
margin back to the previous {\tt BEGIN.} Keep doing this, ignoring
{\tt BEGINs} which have already been used. This matches the {\tt BEGINs} and
{\tt ENDs,} showing the scope of iterations and conditional clauses.
It also shows how many times to indent each line.
\example
\sendnotes{BYHAND-draw lines to the left of the code as suggested in text.}
\twocolcode{
(before indentation)⊗(after indentation)\cr
FOR --- DO⊗FOR --- DO\cr
BEGIN⊗\qquad BEGIN\cr
X:=...⊗\qquad X:=\cr
IF ... THEN⊗\qquad IF ... THEN\cr
BEGIN⊗\qquad \qquad BEGIN\cr
X:=...⊗\qquad \qquad X:=...\cr
WRITE...⊗\qquad \qquad WRITE...\cr
END⊗\qquad \qquad END\cr
ELSE⊗\qquad ELSE\cr
BEGIN⊗\qquad \qquad BEGIN\cr
Y:=...⊗\qquad \qquad Y:=...\cr
Z:=...⊗\qquad \qquad Z:=...\cr
END⊗\qquad \qquad END;\cr
WRITE...⊗\qquad WRITE...\cr
END;⊗\qquad END;\cr
}%end of samecode
\bitem Circle the primitive commands, using a different light color.
These would include the assignment and print commands. Also circle declarations.
\bitem Now circle the larger commands all of whose component commands are
circled, checking that each has one of the forms
\startcode
BEGIN $\Cscr↓{1}$;$\Cscr↓{2}$;...;$\Cscr↓{b}$ END
IF ... THEN $\Cscr↓{1}$
IF ... THEN $\Cscr↓{1}$ ELSE $\Cscr↓{2}$
FOR ... DO $\Cscr↓{1}$
WHILE ... DO $\Cscr↓{1}$
\endcode
\noindent
where $\Cscr ↓{1}$, $\Cscr ↓{2}$, $\ldotss$
have already been circled. Watch
for missing or extra semicolons at this stage, and check when you circle
a compound statement that the {\tt BEGIN} and {\tt END} match,
according to the line in the margin.
\vfill\eject
\example
\sendnotes{BYHAND-draw circles around the blocks as suggested in text.}
\startcode
VAR X,U : REAL;
BEGIN
IF --- THEN
WHILE --- DO
BEGIN
X:=Y ;
U:=V
END
ELSE
FOR --- DO
FOR --- DO
IF --- THEN
WRITE(---)
ELSE
PRINT(---) ;
P:=Q ;
PRINT(---)
END.
\endcode
\bitem Check that all variables used are declared correctly.
\bitem If a variable is used to hold a value at the end of an iteration which
will be needed when the iteration is started the next time (for example,
the sum of a series), check that the variable is always initialized before
entering the iteration.
\rule{
After typing in your program originally, create a paper listing (``hard copy'') of it and
desk check it before trying to run it.
}
\specialbegin{Diagnosing Incorrect Results of Programs}
\sendindex{Diagnosing Incorrect Results}
\bitem If the program has survived translation, but gives
unexpected results, observe how far the program gave correct results.
The error will ordinarily lie between that part of the program and the
part that failed to do or print what you expected. The earliest
symptom is usually the easiest to diagnose, because the effects of the
first error often complicate the later ones.
\bitem If you can't see what went wrong, get a more complete picture of what the
program is doing. At the bottom of each iteration, put
\wuncode{IF DEBUG=1 THEN WRITELN('some message',IV,X,Y,Z)}
where ``some message'' identifies the current iteration, % Maybe put \bitemindent
{\tt IV} is the iteration variable of the iteration, and
{\tt X, Y}, and {\tt Z} represent
any other relevant variables in the current iteration.
Start the program with {\tt DEBUG:= 1}. \sendindex{DEBUG:= 1}
Plan to ``turn off'' these commands by {\tt DEBUG:= 0}
\sendindex{DEBUG:= 0} when the program runs correctly.
\bitem To use the results of such diagnostic prints, check whether the variables
satisfy their intended relations. Is there a variable that doesn't change
when it should? Do the variables have the right sign? Does the printed
value contain a decimal point? (An easy mistake is to declare a variable
{\tt INTEGER} which should be {\tt REAL}.)
\bitem Before accepting a program as correct, make sure that every part gets
executed at least once. Use it on data that cause it to try
both branches of each conditional command, for instance.
\bitem If it is too hard to follow what the program is doing on the assigned
data, change it to do an analogous but smaller problem. Instead
of computing
$$1 + 1/2 + 1/3 + \cdots + 1/10000,$$
\bitemindent compute
$$1 + 1/2 + 1/3 + \cdots + 1/N,$$
\bitemindent and use
\wuncode{N := 4}
\bitemindent at the start of the program;
later, change the 4 to 10000. Where possible, test the
program on data for which you know or can check the results.
\bitem Don't make random changes in your program just to see if something will
happen. Even if it makes your program give correct results on the given
data (it seldom will), it usually leaves the program with bugs. If
necessary, rethink the design of the program and write it out again from
scratch. I once did that for a 4000-line program, and saved myself much
labor by not having to find all the bugs in my junky first draft. In the
process, I was able to simplify the program and make it more efficient.
\specialbegin{Design of Conditional Commands}
Let us design a program to print on one page an ornamental letter B,
as shown in the diagram below.
\fakfigure{170}{} % Figure Title goes between ending {}'s.
The first part of the diagram shows how the letter should appear; the second
shows the geometrical parameters of the shaded region. The letter is assumed
to be symmetrical about its horizontal center line, and all the lines are
assumed to be one inch wide. We recall that the computer prints characters at
a vertical spacing of one sixth of an inch, and a horizontal spacing of one
tenth of an inch. We shall use asterisks ({\tt *}) to fill the shaded area of the
letter. The dot at the center of the left edge of the ``B'' will be used as
the origin of a Cartesian coordinate system.
In outline, a program to print such a letter might be:
\startcode
FOR L:=1 TO 60 DO (* PRINT THE L-TH LINE ON THE PAGE *)
BEGIN
FOR C:=1 TO 132 DO (* PRINT THE C-TH CHARACTER ON THE LINE *)
1. Choose between printing a blank and an asterisk as
the C-th character of the L-th line of the page;
WRITELN
END
\endcode
We are left with the problem of deciding whether
the character at a given row and column of the page is inside the shaded region
or not. A first step is to determine the Cartesian coordinates of the point
at which the character will be printed. We simplify the problem slightly by
taking into account the symmetry; we take the absolute value of the vertical
coordinate, since the decision for the point $(x,y)$ is the same as for the
point $(x,-y)$; this is why we placed the origin on the letter's horizontal
axis of symmetry. We now express the central iterated command of the program
as
\startcode
(* 1 *)
VAR X,Y : REAL; (*this line goes at top of program*)
BEGIN
X := (C-40)/10;
Y := ABS(L-30.5)/6;
(* THE ORIGIN LIES BETWEEN THE 30TH AND 31ST
LINES, AT THE 40TH COLUMN, AND C-40 IS THE
NUMBER OF COLUMNS RIGHT OF THE ORIGIN WE ARE,
AT 10 COLUMNS PER INCH. *)
1.1 Choose between printing a blank and an asterisk at the
point (X,Y) on the page, where Y $≥$ 0.
END.
\endcode
% B example continued.
Here, however, we need only consider values of {\tt X,Y} which fall in the rectangle shown below:
\fakfigure{120}{} % Figure Title goes between ending {}'s.
\noindent
We may observe that this figure consists of straight lines in the region
{\tt X $≤$ 5}, and curved lines in the region {\tt X $>$ 5}; thus a natural first step
is to test whether {\tt X $>$ 5} or not. We then have
\startcode
(* 1.1 *)
IF X > 5 THEN
1.1.1 Choose between printing a blank and an asterisk
for (X,Y) known to be in region B of the diagram below
ELSE
1.1.2 Choose between blank and asterisk for (X,Y)
in region A
\endcode
\fakfigure{120}{} % Figure Title goes between ending {}'s.
The first test can easily be rewritten, first calculating the distance
from the common center of the circles:
\startcode
(* 1.1.1 *)
%I changed line must be placed to line is put cuz always got overflow
VAR DISTANCE :REAL;(*This line is placed among the declarations*)
BEGIN
DISTANCE := SQRT(SQR(X-5) + SQR(Y-1.75));
IF DISTANCE > 2.25 THEN WRITE(' ')
ELSE BEGIN (* DISTANCE <= 2.25 *)
IF DISTANCE >= 1.25 THEN WRITE('*')
ELSE (* DISTANCE < 1.25 *)
WRITE (' ')
END
\endcode
The second test may be further simplified by separating it into two cases,
according as {\tt Y $≥$ 3} or {\tt Y $<$ 3}:
\startcode
(* 1.1.2 *)
IF Y >= 3 THEN
1.1.2.1 Choose between blank and asterisk for a point
known to be in region AA
ELSE
1.1.2.2 Choose for a point known to be in region AB
END
\endcode
% B example continued.
\fakfigure{120}{} % Figure Title goes between ending {}'s.
\noindent
After a final decomposition of the remaining tests, we have the program which
follows:
\startcode
BEGIN
FOR L:= 1 TO 60 DO (* PRINT L-TH LINE *)
BEGIN
FOR C:=1 TO 132 DO (* PRINT C-TH CHARACTER *)
BEGIN
X := (C-40)/10;
Y := ABS((L-30.5)/6);
(* THE ORIGIN LIES BETWEEN THE 30TH AND 31ST LINES, AT THE
40TH COLUMN *)
\endcode
\startcode
IF X > 5 THEN (* REGION B *)
BEGIN
DISTANCE := SQRT((SQR(X-5)+SQR(Y-1.75)));
IF DISTANCE > 2.25 THEN WRITE(' ')
ELSE (* DISTANCE <= 2.25 *)
IF DISTANCE >= 1.25 THEN WRITE('*')
ELSE (* DISTANCE < 1.25 *)
WRITE(' ')
END
ELSE (* REGION A *)
IF Y >= 3 THEN
IF Y > 4 THEN WRITE(' ')
ELSE IF X >= -1 THEN WRITE('*')
ELSE WRITE(' ')
ELSE IF X < 0 THEN WRITE(' ')
ELSE IF X <= 1 THEN WRITE('*')
ELSE IF Y > 0.5 THEN WRITE(' ')
ELSE WRITE('*')
END ;
WRITELN
END
END .
\endcode
The above example illustrates that a complicated decision can often be
expressed as a series of tests, each of a simple condition. In a command of
the form
\wuncode{IF $\Escr$ THEN $\Cscr ↓1$ ELSE $\Cscr ↓2$}
it is possible to simplify the design of $\Cscr↓{1}$ by using the knowledge that when
$\Cscr↓{1}$ is executed, we know that $\Escr$ is true; similarly, in designing $\Cscr ↓{2}$, we
need treat only the case that $\Escr$ is false. Often, there is a choice of what
condition to test first. The resulting program is simplest if the condition
is so chosen that, as far as possible, no other condition need be tested in
both $\Cscr↓{1}$ and $\Cscr↓{2}$.
% B example continued.
\exercise
Simplify the above program by using the logical connectives in the conditions.
For example, the five lines following the computation of {\tt DISTANCE}
could be written
\startcode
IF (DISTANCE > 2.25) OR (DISTANCE < 1.25) THEN
WRITE(' ')
ELSE WRITE('*')
\endcode
\endexercise
\exercise
Print another letter, perhaps {\tt F} or {\tt N} or {\tt R}, in a similar fashion.
\endexercise
\exercise
Print such a letter in italic (slanting) style.
\endexercise
\specialbegin{Avoiding Redundant Effort in Programming}
\sendindex{Redundant Effort}
\sendnotes{See REJECT.TEX[105,CSD] for old text.}
Suppose we want to compute $e↑x$ approximately for a small value of
$x$, using the formula:
$$e↑x \approx 1 +{x\over1!}+{x↑{2}\over2!}+{x↑{3}\over3!}+{x↑4\over4!}+\cdots+{x↑9\over9!}$$
The most obvious method uses an outer iteration to run through the terms which
are being added, and an inner iteration to calculate the factorials. This
involves much wasted effort, because when we have computed 3! we don't
have to start from scratch to compute 4!; we only have to multiply 3!
by 4. In fact, once we have $x↑3/3!$, we only have to multiply by $x$ and
divide by 4 to get $x↑4/4!$. A program based on this follows:
\startcode
(declarations)
BEGIN
READ(X);
SUM := 1;
TERM := 1;
FOR I:=1 TO 9 DO
BEGIN
TERM := TERM * X/I; (* X**I/I! *)
SUM := SUM + TERM (* SUM OF TERMS UP TO DEGREE I *)
END;
END.
\endcode
The general idea is to record all the useful information that can be kept from
the part of the computation done so far.
The variable {\tt TERM} holds enough useful information that we can get the new
summand at the next value of {\tt I} with just a multiplication and division.
% Again, we have arranged to keep all the information we can for later use.
Let's try doing the same thing with a more complicated formula, for
$\pi/6$:
\sendnotes{BYHAND- circle the appropriate parts of each summand.}
$$arcsin\left({1\over2}\right)={1\over2}+{1\over2↑{3}\cdot2\cdot3}+{1\cdot3\over2↑{5}\cdot2\cdot4\cdot5}+\!
{1\cdot3\cdot5\over2↑7\cdot2\cdot4\cdot6\cdot7}+\cdots$$
where we have circled the part of each summand that is useful in computing
the next one to the right. To compute this by hand, we might set up this
table:
\sendnotes{BYHAND- Insert the appropriate arrows.}
{\lineskip 8 pt% to get more vertical space in table
\threecolalign{
\quad Q⊗C⊗\quad S\cr
$\dispstyle{1\over2}$⊗1⊗$\dispstyle{1\over2}$\cr
$\dispstyle{1\over2↑{3}\cdot2}$⊗3⊗$\dispstyle{{1\over2}+{1\over2↑{3}\cdot2\cdot3}}$\cr
$\dispstyle{1\cdot3\over2↑{5}\cdot2\cdot4}$⊗5⊗$\dispstyle{{1\over2}+{1\over2↑{3}\cdot2\cdot3}+{1\cdot3\over2↑{5}\cdot2\cdot4\cdot5}}$\cr
$\dispstyle{{1\cdot3\cdot5\over2↑{7}\cdot2\cdot4\cdot6}}$⊗7⊗$\dispstyle{{1\over2
}+\cdots+{1\cdot3\cdot5\over2↑{7}\cdot2\cdot4\cdot6\cdot7}}$\cr
⊗etc.⊗\cr
}%end of threecolalign
}%end of lineskip
In each row after the first, we get the number in column $Q$ from the
one above it by multiplying by $C/(4(C+1))$, where $C$ is the number in
column $C$ on the line above. We get the number in column $C$ by adding
$2$ to the one above. We get the number in column $S$
by adding $Q/C$ (from
the same row) to the number above in column $S$. The arrows show where the
information comes from that is used to compute each of the numbers. No
number is used again after the number below it is calculated. Because of
this, we can design a computer program to do the same calculations, using
one variable for each column.
\startcode
(declarations)
BEGIN
(initialization)
FOR I:=1 TO BIGENOUGH DO
BEGIN
Q := Q*C/(4*(C+1));
C := C+2;
S := S + Q/C
END;
WRITE('PI/6=',S)
END.
\endcode
A way to do this kind of problem systematically starts by deciding what
we need to compute each time through the iteration. For example, the third
time through, we want to end up with
$${1\over2}+{1\over2↑{3}\cdot2\cdot3}+{1\cdot3\over2↑{5}\cdot2\cdot4
\cdot5}+{1\cdot3\cdot5\over2↑{7}\cdot2\cdot4\cdot6\cdot7}$$
In order to get it and to save the useful information needed for the next
stage, we must not only have the sum of the first three terms (left from the
second time through) but also the values
$${1\cdot3\cdot5\over2↑{7}\cdot2\cdot4\cdot6}$$
(to be saved
for use the next time through) and $7$. We want to give these three values to
variables, assuming that the corresponding values were left in those variables
the previous time through the iteration. That is, assume that before the
iteration, we have
{\lineskip 8 pt% to get more vertical space in table
\threecolctralign{
Q⊗C⊗S\cr
%***need blank line here
${\dispstyle{1\cdot3\over2↑{5}\cdot2\cdot4}}$
⊗$5$
⊗$\dispstyle{{1\over2}+{1\over2↑{3}\cdot2\cdot3}
+{1\cdot3\over2↑5\cdot2\cdot4\cdot5}}$\cr
}%end threecolalign
}%end of lineskip
and we want to make
{\lineskip 8 pt% to get more vertical space in table
\threecolctralign{
Q⊗C⊗S\cr
%***need blank line here
$\dispstyle{{1\cdot3\cdot5\over2↑{7}\cdot2\cdot4\cdot6}}$
⊗$7$
⊗$\dispstyle{{1\over2}+{1\over2↑{3}\cdot2\cdot3}
+{1\cdot3\cdot5\over2↑7\cdot2\cdot4\cdot6\cdot7}}$\cr
}%end threecolalign
}%end of lineskip
The two lines above, which describe what each of the variables holds at a
certain moment of the computation, are called {\sl snapshots}.
\sendindex{snapshots} Often, the design
of an iteration is best approached by asking what the typical snapshot should
look like, remembering that each one has to contain enough information to
allow computing the next one. When we have designed the typical one, we work
back to the first one, and the program now is schematically:
\startcode
Assign the variables the values they need for the first snapshot;
FOR I:= 2 TO N DO
From the values in snapshot I-1, compute and assign the values
the variables require in snapshot I.
\endcode
\noindent
Another snapshot example: look at the series of numbers
$$0, 0, 0, 1, 1, 2, 3, 6, 10, 18, 31, 55, \ldots$$
where each number after the fourth is the sum of the numbers four places to
its left, two places to its left, and one place to its left; for example,
$2+6+10 = 18$. A snapshot that works in computing this series of numbers,
consists of five consecutive numbers, of which four are leftovers from the
previous stage, and the fifth is obtained by adding the first, second, and
fourth: from $A = 1, B = 2, C = 3, D = 6, E = 10$, we want to get
$A = 2, B = 3, C = 6, D = 10, E = 18$, which can be done by
\startcode
A := B ;
B := C ;
C := D ;
D := E ;
E := A+C+D
\endcode
\noindent
A complete program is then
\startcode
(declarations)
BEGIN
A:=0;B:=0;C:=0;D:=1;E:=1;
WRITE(A,B,C,D,E);
FOR I:=6 TO BIGENOUGH DO
BEGIN
A:=B; B:=C; C:=D; D:=E;
E := A+C+D;
WRITELN(E)
END
END.
\endcode